package com.yiwenup.leetcode.offer_ii;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @PROJECT struct-algorithm
 * @PACKAGE com.yiwenup.leetcode.offer_ii
 * @Author yiwenup
 * @Date 2022-02-19 17:11:11
 * <p>
 * @DESCRIPTION {https://leetcode-cn.com/problems/VvJkup/}
 *
 * <pre>
 *     输入：nums = [1,2,3]
 *     输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
 * </pre>
 */
public class No083 {

    private List<List<Integer>> res = new ArrayList<>();
    private List<Integer> temp = new ArrayList<>();

    /**
     * 执行用时：1 ms, 在所有 Java 提交中击败了73.46%的用户
     * 内存消耗：41.3 MB, 在所有 Java 提交中击败了20.20%的用户
     */
    public List<List<Integer>> permute(int[] nums) {
        if (nums == null || nums.length == 0) return res;
        for (int num : nums) temp.add(num);

        dfs(temp, 0, temp.size());

        return res;
    }

    private void dfs(List<Integer> temp, int begin, int end) {
        if (begin == end) {
            res.add(new ArrayList<>(temp));
            return;
        }

        for (int i = begin; i < end; i++) {
            Collections.swap(temp, begin, i);
            dfs(temp, begin + 1, end);
            Collections.swap(temp, begin, i);
        }
    }

}
